package Leetcode.树;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: kirito
 * @Description:
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
 *
 * 思路1：
 *      直接先序遍历，然后组成链表？  ==》先序遍历的过程就直接连成链表咋样
 *
 *     1
 *    / \
 *   2   5
 *  / \   \
 * 3   4   6
 *
 * //将 1 的左子树插入到右子树的地方
 *     1
 *      \
 *       2         5
 *      / \         \
 *     3   4         6
 * //将原来的右子树接到左子树的最右边节点
 *     1
 *      \
 *       2
 *      / \
 *     3   4
 *          \
 *           5
 *            \
 *             6
 *
 *  //将 2 的左子树插入到右子树的地方
 *     1
 *      \
 *       2
 *        \
 *         3       4
 *                  \
 *                   5
 *                    \
 *                     6
 *
 *  //将原来的右子树接到左子树的最右边节点
 *     1
 *      \
 *       2
 *        \
 *         3
 *          \
 *           4
 *            \
 *             5
 *              \
 *               6
 *
 * @Date: 2024/2/29 13:15
 * @Version: 1.0
 */

public class 二叉树展开为链表 {
    //擦。。void。。。我想想。。。
    //那就是直接操作这棵树，并不是转成链表
    public void flatten(TreeNode root) {
        while (root != null) {
            //左子树为 null，直接考虑下一个节点
            if (root.left == null) {
                root = root.right;
            } else {
                // 找左子树最右边的节点
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                //将原来的右子树接到左子树的最右边节点
                pre.right = root.right;
                // 将左子树插入到右子树的地方
                root.right = root.left;
                root.left = null;
                // 考虑下一个节点
                root = root.right;
            }
        }
    }

    /**
     * 直接前序遍历  然后逐步添加
     * @param root
     */
    public void flatten2(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }

}
